package pri.zjy.dynamicProgramming;

/**
 * @author zhangjy
 * @description 打家劫舍
 * @date 2025/5/26 20:50
 */
public class Rob_198 {

    public static void main(String[] args) {
        Rob_198 rob198 = new Rob_198();

//        int[] nums = {1, 2, 3, 1};
        int[] nums = {2, 1, 1, 2};
        System.out.println(rob198.rob(nums));
        System.out.println(rob198.rob2(nums));
    }

    /**
     * 个人解法：dp
     * <p>
     * dp[i]，表示偷第 i 号房的前提下，能偷到的最高金额
     */
    public int rob2(int[] nums) {
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);

        // 1.dp[i]，表示偷第 i 号房的前提下，能偷到的最高金额
        // i从0开始
        int[] dp = new int[nums.length];

        // 2.递推公式
        // dp[i] = Math.max(dp[i - 2], dp[i - 3]) + nums[i];
        // 第i号必偷的前提下，i-2或i-3都可以偷，选择金额更大的一个来偷

        // 3.初始化
        // 根据dp[i]定义，那么必偷第0号，或者第1号房时，其最大金额就为该房间的金额，那么dp[2]就是偷第0、1号房间和只偷第2号房的最大值
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = Math.max(nums[0] + nums[2], nums[1]);

        // 4.遍历
        for (int i = 3; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2], dp[i - 3]) + nums[i];
            // 5.打印
            if (dp[i - 2] > dp[i - 3]) {
                System.out.println("dp[" + i + "]=" + dp[i] + " = " + "dp[" + (i - 2) + "]=" + dp[i - 2] + " + " + "nums[" + i + "]=" + nums[i]);
            } else {
                System.out.println("dp[" + i + "]=" + dp[i] + " = " + "dp[" + (i - 3) + "]=" + dp[i - 3] + " + " + "nums[" + i + "]=" + nums[i]);
            }

        }

        // 最高金额可能偷最后一间房，也可能投倒数第二间
        return Math.max(dp[nums.length - 1], dp[nums.length - 2]);
    }

    /**
     * dmsxl：dp
     * <p>
     * dp[i]，表示考虑偷第 i 号房的前提下（第i号、第i-1号选择一个金额更大的偷），能偷到的最大金额
     */
    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);

        // 1.dp[i]，表示考虑偷第 i 号房，能偷到的最高金额
        int[] dp = new int[nums.length];

        // 2.递推公式
        // 偷i-1号，就不能偷第i号；偷第i号，得到的金额总和，就是i-2号 + 第i号房间的金额；两者选最大值作为dp[i]的值。
        // dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])

        // 3.初始化
        // 根据dp数组定义，dp[1]表示考虑偷第 1 号房能偷到的最高金额，所以要看第0、1号房的金额
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        // 4.遍历
        // dp数组依赖于前面两项，所以从前往后遍历
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
            // 5.打印
            if (dp[i - 1] > dp[i - 2] + nums[i]) {
                // 偷第i-1号房
                System.out.println("dp[" + i + "]=" + dp[i] + " = " + "dp[" + (i - 1) + "]=" + dp[i - 1]);
            } else {
                // 偷第i号房
                System.out.println("dp[" + i + "]=" + dp[i] + " = " + "dp[" + (i - 2) + "]=" + dp[i - 2] + " + " + "nums[" + i + "]=" + nums[i]);
            }

        }

        return dp[nums.length - 1];
    }

}
